package com.yuanzhi.train.tree;

/**
 * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。 高度平衡
 * 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。  
 *
 * 示例 1： 输入：nums = [-10,-3,0,5,9] 输出：[0,-3,9,-10,null,5]
 * 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
 *
 * 示例 2： 输入：nums = [1,3] 输出：[3,1] 解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。  
 *
 * 提示： 1 <= nums.length <= 104 -104 <= nums[i] <= 104 nums 按 严格递增 顺序排列
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 
 * @author yuanZhi
 * @since 2022/1/20 14:04
 */
public class SortedArrayToBST {
	public static void main(String[] args) {
		int[] arr = {-10, -3, 0, 5, 9};
		System.out.println(sortedArrayToBST(arr));
	}

	private static TreeNode sortedArrayToBST(int[] arr) {
		if (arr == null){
			return new TreeNode();
		}
		return buildTree(arr, 0, arr.length - 1);
	}

	/**
	 * 根节点确定为中间节点（数组已经升序排好序）
	 * 1、[-10, -3, 0, 5, 9]，0--》root
	 * 2、确定1中root的左右子树的root
	 * 		此时数组被分成了[-10, -3]和[5, 9]
	 * 		所以其实就是一个范围内，左子树的中点一直在不断的前移，右子树的中点一直在不断后移
	 * 3、重复1和2的操作
	 * @param arr 数组
	 * @param left 左边位置（对于左子树即为第一个，对于右子树便是当前中点的后一个）
	 * @param right 右边位置（对于左子树即为当前中点的前一个，对于右子树便是最后一个）
	 */
	private static TreeNode buildTree(int[] arr, int left, int right){
		if (left > right){
			return null;
		}
		int mid = (left + right) / 2;
		TreeNode root = new TreeNode(arr[mid]);
		root.left = buildTree(arr, left, mid -1);
		root.right = buildTree(arr, mid + 1, right);

		return root;
	}
}
